package two.chapter_1.c1_4;

import edu.princeton.cs.algs4.StdOut;
import sun.font.CompositeGlyphMapper;
import two.chapter_1.c1_1.Printer;

public class Ex1_4_19 {


    public static void main(String[] args) {

        int [][]a ={{0 ,1 ,0 ,1, 0 ,1},{1 ,0, 1, 0, 1, 0},{0 ,1, 0, 1, 0, 1},{ 1,0, 1, 0, 1, 0}};
        //matrixNumlocal(a);

        int[][] matrix =
        {
            { 26, 3 , 4 , 10, 11 },
            { 10, 8 , 6 , 3 , 13 },
            { 11, 10, 9 , 14, 15 },
            { 16, 17, 18, 27, 20 },
            { 21, 22, 23, 24, 25 }
        };
        matrixNumlocal(matrix);
       StdOut.println(MinimumRow(matrix, 0, 5, 0, 5));
    }


    /**
     * N*N的二维数组
     * 矩阵的局部最小元素
     * a[i][j]<a[i+1][j]
     * a[i][j]<a[i][j+1]
     * a[i][j]<a[i-1][j]
     * a[i][j]<a[i][j-1]
     *
     *
     *        1                        0 1 0 1 0 1
     *      1 0 1  最小单位是3*3子矩阵   1 0 1 0 1 0
     *        1                        0 1 0 1 0 1
     *                                 1 0 1 0 1 0
     *
     * 平方级别
     * @param a
     */
    private static void matrixNumlocal(int a[][]){
        int N=a.length;

        for (int i=0;i<N-2;i++){
            for (int j=0;j<N-2;j++) {
                int x = i + 1;
                int y=j+1;
                int mid = a[x][y];
                if (mid < a[x + 1][y] && mid < a[x][y + 1] && mid < a[x - 1][y] && mid < a[x][y - 1]) {
                    StdOut.println("x:"+x+" y:"+y);
                }
            }
        }

    }

    /**
     *   1 0 1 0 1 0 1 0 1 0
     *   1 0 1 0 1 0 1 0 1 0
     *   1 0 1 0 1 0 1 0 1 0
     *   1 0 1 0 1 0 1 0 1 0
     *   1 0 1 0 1 0 1 0 1 0
     *   1 0 1 0 1 0 1 0 1 0
     *   1 0 1 0 1 0 1 0 1 0
     *   1 0 1 0 1 0 1 0 1 0
     *   1 0 1 0 1 0 1 0 1 0
     *   1 0 1 0 1 0 1 0 1 0
     * @param row
     * @param rowLen
     * @param col
     * @param colLen
     * @param a
     *
     */
    private static void matrixNumlocalFast(int row,int rowLen,int col,int colLen,int a[][]){


    }



    static int MinimumRow(int[][] matrix, int rowStart, int rowLength, int colStart, int colLength)
    {
        int min = Integer.MAX_VALUE;
        if (rowLength < 3)
            return Integer.MAX_VALUE;
        int mid = rowStart + rowLength / 2;
        int minCol = 0;
        // 获取矩阵中间行的最小值
        for (int i = 0; i < colLength; ++i)
        {
            if (min > matrix[mid][ colStart + i])
            {
                min = matrix[mid][ colStart + i];
                minCol = i;
            }
        }
        // 检查是否满足条件
        if (matrix[mid][minCol] < matrix[mid - 1][ minCol] && matrix[mid][ minCol] < matrix[mid + 1][ minCol])
        {
            return matrix[mid][ minCol];
        }
        // 如果不满足则向较小一侧移动
        if (matrix[mid - 1][minCol] > matrix[mid + 1][ minCol])
        {
            return MinimumCol(matrix, rowStart, rowLength, mid + 1, colLength / 2 + 1);
        }
            else
        {
            return MinimumCol(matrix, rowStart, rowLength, colStart, colLength / 2 + 1);
        }
    }

    /// <summary>
    /// 在矩阵中间列查找局部最小。
    /// </summary>
    /// <param name="matrix">矩阵。</param>
    /// <param name="rowStart">实际查找范围的行起始。</param>
    /// <param name="rowLength">实际查找范围的行结尾。</param>
    /// <param name="colStart">实际查找范围的列起始。</param>
    /// <param name="colLength">实际查找范围的列结尾。</param>
    /// <returns>矩阵中的局部最小元素。</returns>
    static int MinimumCol(int[][] matrix, int rowStart, int rowLength, int colStart, int colLength)
    {
        int min = Integer.MAX_VALUE;
        int n = matrix.length;
        int mid = n / 2;
        int minRow = 0;

        // 获取矩阵中间列最小值
        for (int i = 0; i < n; ++i)
        {
            if (min > matrix[i][ mid])
            {
                min = matrix[i][ mid];
                minRow = i;
            }
        }
        // 检查是否满足条件
        if (matrix[minRow][ mid] < matrix[minRow][ mid - 1] && matrix[minRow][ mid] < matrix[minRow][ mid + 1])
        {
            return matrix[minRow][mid];
        }
        // 如果不满足则向较小一侧移动
        if (matrix[minRow][ mid - 1] > matrix[minRow][ mid + 1])
        {
            return MinimumRow(matrix, mid + 1, rowLength / 2 + 1, colStart, colLength);
        }
            else
        {
            return MinimumRow(matrix, rowStart, rowLength / 2 + 1, colStart, colLength);
        }
    }
}
